package com.dyz.topics.dynamicProgramming;

import java.util.Arrays;

public class CoinChange322 {
    public int coinChange(int[] coins, int amount) {
        if(amount==0){return 0;}
        int[]dp = new int[amount+1];

        for(int coin:coins){
            //从coin开始，
            for(int j=coin; j<=amount; j++){
                //相等的时候，最小就是1
                if(j==coin){
                    dp[j]=1;
                }else if(dp[j]==0 && dp[j-coin]!=0){
                    dp[j]=dp[j-coin]+1;
                }else if(dp[j-coin]!=0){//如果dp[j]!=0,需要j与j-coin相互比较
                    dp[j] = Math.min(dp[j], dp[j-coin]+1);
                }
            }
        }
        return dp[amount]==0?-1:dp[amount];
    }

    public int coinChange1(int[] coins, int amount) {
        if(amount==0){return 0;}
        int[]dp = new int[amount+1];
        Arrays.fill(dp, Integer.MAX_VALUE);
        dp[0]=0;
        for(int i =0; i<=amount;i++){
            for(int coin:coins){
                int leftAcount = i-coin;
                if(leftAcount<0 || dp[leftAcount]==Integer.MAX_VALUE){continue;}
                dp[i] = Math.min(dp[i], dp[leftAcount]+1);
            }
        }
        return dp[amount]==Integer.MAX_VALUE?-1:dp[amount];
    }
}
